#include "BinaryTree.h"
#include <iostream>
#include <MyInclude/LinkQueue.h>

BinaryTree::BinaryTree()
{
    root = nullptr;
}

BinaryTree::~BinaryTree()
{
    FreeNode(root);
}

void BinaryTree::Insert(const ElementType &element)
{
    root = InsertNode(root, element);
}

void BinaryTree::Remove(const ElementType &element)
{
    root = RemoveNode(root, element);
}

BinaryTree::ElementType* BinaryTree::Find(const ElementType &element)
{
    return FindNode(root, element);
}

void BinaryTree::show()
{
    std::cout<<"前序遍历:";
    PrevTravel(root);
    std::cout<<std::endl;

    std::cout<<"中序遍历:";
    MidTravel(root);
    std::cout<<std::endl;

    std::cout<<"后序遍历:";
    PostTravel(root);
    std::cout<<std::endl;

    std::cout<<"层序遍历:";
    LinkQueue q;
    q.Push(root);
    while(!q.IsEmpty())
    {
        TreeNode* node = (TreeNode*)*q.GetFront();
        q.Pop();
        std::cout<<node->data<<" ";
        if(node->left)
        {
            q.Push(node->left);
        }
        if(node->right)
        {
            q.Push(node->right);
        }
    }
    std::cout<<std::endl;
}

BinaryTree::TreeNode* BinaryTree::InsertNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr)  //节点为空
    {
        return new TreeNode(element);
    }

    if(node->data == element)  //数据已经存在
    {
        return node;
    }
    else if(node->data > element)  //数据小于当前节点
    {
        node->left = InsertNode(node->left, element);
        //左边重
        if(LRDevition(node) > 1)
        {
            //左左失衡
            if(node->left->data > element)
            {
                //右旋
                node = RotateRight(node);
            }
            //左右失衡
            else
            {
                //左右旋
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right = InsertNode(node->right, element);
        //右边重
        if(LRDevition(node) < -1)
        {
            //右右失衡
            if(node->right->data < element)
            {
                //左旋
                node = RotateLeft(node);
            }
            //右左失衡
            else
            {
                //右左旋
                node = RotateRightLeft(node);
            }
        }
    }
    return node;
}

void BinaryTree::PrevTravel(TreeNode *node)
{
    if(node == nullptr)
    {
        return;
    }
    std::cout<<node->data;
    PrevTravel(node->left);
    PrevTravel(node->right);
}

void BinaryTree::MidTravel(TreeNode *node)
{
    if(node == nullptr)
    {
        return;
    }
    MidTravel(node->left);
    std::cout<<node->data;
    MidTravel(node->right);
}

void BinaryTree::PostTravel(TreeNode *node)
{
    if(node == nullptr)
    {
        return;
    }
    PostTravel(node->left);
    PostTravel(node->right);
    std::cout<<node->data;
}

void BinaryTree::FreeNode(TreeNode *node)
{
    if(node == nullptr)
    {
        return;
    }
    FreeNode(node->left);
    FreeNode(node->right);
    delete node;
}

BinaryTree::TreeNode* BinaryTree::RemoveNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr)
    {
        return nullptr;
    }
    if(node->data < element)  //数据大于当前节点
    {
        node->right = RemoveNode(node->right, element);
    }
    else if(node->data > element) //数据小于当前节点
    {
        node->left = RemoveNode(node->left, element);
    }
    else
    {
        //叶子
        if(node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        //有两个孩子
        else if(node->left != nullptr && node->right != nullptr)
        {
            //取右子树中的最小结点
            TreeNode *minNode = GetMinNode(node->right);
            node->data = minNode->data;
            //删除右子树中的最小结点
            node->right = RemoveNode(node->right, minNode->data);
        }
        //只有一个孩子
        else
        {
            TreeNode *child = node->left ? node->left : node->right;
            delete node;
            return child;
        }
    }

    //左边重
        if(LRDevition(node) > 1)
        {
            //左左失衡
            if(LRDevition(node->left) > 0)
            {
                //右旋
                node = RotateRight(node);
            }
            //左右失衡
            else
            {
                //左右旋
                node = RotateLeftRight(node);
            }
        }

    //右边重
        if(LRDevition(node) < -1)
        {
            //右右失衡
            if(LRDevition(node->right) < 0)
            {
                //左旋
                node = RotateLeft(node);
            }
            //右左失衡
            else
            {
                //右左旋
                node = RotateRightLeft(node);
            }
        }

    return node;
}

BinaryTree::TreeNode* BinaryTree::GetMinNode(TreeNode *node)
{
    TreeNode *minNode = node;
    while(minNode->left)
    {
        minNode = minNode->left;
    }
    return minNode;
}

BinaryTree::ElementType *BinaryTree::FindNode(TreeNode *node,const ElementType &element)
{
    if(node == nullptr)
        return nullptr;
    
    if(node->data == element)
    {
        return &node->data;
    }
    else if(node->data > element)
    {
        return FindNode(node->left, element);
    }
    else
    {
        return FindNode(node->right, element);
    }
}

BinaryTree::TreeNode *BinaryTree::RotateRight(TreeNode *root)
{
    TreeNode *t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}

BinaryTree::TreeNode *BinaryTree::RotateLeft(TreeNode *root)
{
    TreeNode *t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}

BinaryTree::TreeNode *BinaryTree::RotateLeftRight(TreeNode *root)
{
    //左子树左旋
    root->left = RotateLeft(root->left);
    return RotateRight(root);  //整棵树右旋
}

BinaryTree::TreeNode *BinaryTree::RotateRightLeft(TreeNode *root)
{
    //右子树右旋
    root->right = RotateRight(root->right);
    return RotateLeft(root);  //整棵树左旋
}

int BinaryTree::GetNodeHeight(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    int leftHeight = GetNodeHeight(node->left);
    int rightHeight = GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int BinaryTree::LRDevition(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
} 
